\vspace{-0.15in}
\section{Preliminaries}
\vspace{-0.15in}
Let $G$ be a connected graph with vertex set $V$ and edge set $E$, and let $|V| = n$. We define a coalescing-branching (cobra) random walk on $G$ with branching factor $k$ starting at some arbitrary $v \in V$ as follows: At time $t = 0$ we place a pebble at $v$. Then in the next and every subsequent time step, every pebble in $G$ clones itself $k-1$ times (so that there are now $k$ pebbles at each vertex that originally had a pebble). Each pebble independently selects a neighbor of its current vertex uniformly at random and moves to it. Once all pebbles make their one-hop moves, if two pebbles are at the same vertex they coalesce into a single pebble, and the next round begins. In a cobra-walk, a vertex can be active an arbitrary number of times. 

For a time step $t$ of the process, let $S_t$ be the \textbf{active set}, the set of all vertices of $G$ that have a pebble. We will use two different definitions of the neighborhood of $S_t$: Let $N(S_t)$ be the \textbf{inclusive} neighborhood, the union of the set of neighbors of all vertices in $S_t$ (which can include members of $S_t$ itself). Let $\Gamma(S_t)$ be the \textbf{non-inclusive neighborhood}, which is the union of the set of neighbors of all vertices of $S_t$ such that $S_t \cap \Gamma(S_t) = \emptyset$.  

Let the expected {\bf maximum hitting time} $h_{max}$ of a cobra-walk on $G$ be defined as the $max_{u,v \in V} \E[h_{u,v}]$ where $h_{u,v}$ is the time it takes a cobra-walk starting at vertex $u$ to first reach $v$ with at least one pebble. 

We are interested in two different notions of cover time, the time until all vertices of $G$ have been visited by a cobra-walk at least once. Let $\tau_v$ be the minimum time $t$ such that, for a cobra-walk starting from $v$, $\forall u \in V - {v}$, $u \in S_t$ for some $t \leq \tau_v$. Then we define the \textbf{cover time} of a cobra-walk on $G$ to be $\max_{v \in V} \tau_v$. We define the \textbf{expected cover time} to be $\max_{v \in V} \E[\tau_v]$. Note that in the literature for simple random walks, cover time usually refers to the expected cover times. 
In this paper we will show high-probability bounds on the  cover time.

In Section 6 we will be proving results for cobra-walks on expanders. In this paper, we will use a spectral definition for expanders and then use Tanner's theorem to translate that to neighborhood and cut-based notions of expanders.

\begin{definition}
\label{def:exp}
An \textbf{$\epsilon$ - expander} graph is a $d$-regular graph whose adjacency matrix has eigenvalues such that $|\alpha_i| \leq \epsilon d$ for $i \geq 2$. 
\end{definition}

We also want to define the notion of an $\epsilon$-approximation:
\begin{definition}
\label{def:epsapprox}
$G$ is an \textbf{$\epsilon$-approximation} for a graph $H$ if $(1-\epsilon) H \preccurlyeq G \preccurlyeq (1+\epsilon)H$, where $H \preccurlyeq G$ if for all $x$, $x^{T} L_H x \leq x^{T} L_G x$, where $L_G$ and $L_H$ are the Laplacians of G and H, respectively.
\end{definition} 

Finally, we will rely on the neighborhood expansion of a set $S$ on $G$, where we define $N(S)$ as the inclusive neighborhood. For this we will use Tanner's theorem~\cite{tanner1984explicit}, which gives us a lower bound on the size of the neighborhood of $S$ for sufficiently strong expanders.

\begin{theorem}
\label{exp:tanner}
Let $G$ be a d-regular graph that $\epsilon$-approximates $\frac{d}{n} K_n$. Then for all $S \subseteq V$ with $|S| = \delta n$,
$ |N(S)| \geq \frac{|S|}{\epsilon^2 (1 - \delta) + \delta} \cdot$
\end{theorem}
